package com.fanshuai.tree.btree;

import com.fanshuai.tree.bst.BST;

import java.util.ArrayList;
import java.util.List;

/**
 * B树
 * @param <K>
 * @param <V>
 */
public class BTree<K extends Comparable<K>, V> implements BST<K, V> {
    /**
     * M
     */
    private int M = 6;

    /**
     * 默认M
     */
    private int DEFAULT_M = 6;

    class Entry {
        K key;
        V value;
        Node next;

        public Entry(K key, V value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    class Node {
        /**
         * data M-1
         * pointer M
         */
        Entry[] children;
        /**
         * data size
         * pointer size = n+1
         */
        int n;

        Node parent;

        public Node(int n) {
            this.children = (Entry[]) new Object[M];
            this.n = n;
            parent = null;
        }

        public boolean isLeaf() {
            return n > 0 && children[0].next == null;
        }
    }

    private Node root;
    private int size;
    private int height;

    public BTree(int m) {
        if (m < DEFAULT_M) {
            m = DEFAULT_M;
        }
        this.M = m;

        root = new Node(0);
        size = 0;
        height = 0;
    }

    @Override
    public void put(K key, V value) {
        Entry entry = put(root, key, value, height);
        if (entry == null) {
            return;
        }

        Node node = new Node(1);
        node.children[0].key = entry.key;
        node.children[0].value = entry.value;
        node.children[0].next = root;
        node.children[1].next = entry.next;

        root.parent = node;
        entry.next.parent = node;
        clearEntry(entry);

        root = node;
        height++;
    }

    private Entry put(Node node, K key, V value, int height) {
        Entry entry = null;

        int i;
        for (i = 0; i < node.n; i++) {
            K k = node.children[i].key;
            if (key.compareTo(k) == 0) {
                node.children[i].value = value;
                return null;
            } else if (key.compareTo(k) < 0) {
                break;
            }
        }
        int pos = i;

        if (height == 0) {
            entry = new Entry(key, value, null);
        } else {
            entry = put(node.children[pos].next, key, value, height - 1);
        }

        if (null == entry) {
            return null;
        } else {
            for (i = 0; i < node.n; i++) {
                K k = node.children[i].key;
                if (entry.key.compareTo(k) < 0) {
                    break;
                }
            }
            pos = i;

            for (i = node.n; i >= pos; i--) {
                node.children[i + 1] = node.children[i];
            }
            node.children[pos].key = entry.key;
            node.children[pos].value = entry.value;
            node.children[pos + 1].next = entry.next;
            entry.next.parent = node;
            clearEntry(entry);

            node.n++;
            if (node.n == M - 1) {
                return split(node);
            } else {
                return null;
            }
        }
    }

    private void clearEntry(Entry entry) {
        entry.key = null;
        entry.value = null;
        entry.next = null;
    }

    /**
     * split node
     * @param node
     * @return
     */
    private Entry split(Node node) {
        int mid = (node.n - 1) / 2;
        Entry entry = new Entry(node.children[mid].key, node.children[mid].value, null);

        Node right = new Node(node.n - mid -1);
        for (int i = mid + 1; i < node.n; i++) {
            right.children[i - mid - 1] = node.children[i];
            node.children[i] = null;
        }
        right.children[node.n - mid -1] = node.children[node.n];
        node.children[node.n] = null;

        node.children[mid].key = null;
        node.children[mid].value = null;
        node.n = mid;

        entry.next = right;
        return entry;
    }

    @Override
    public V get(K key) {
        return get(root, key, height);
    }

    private V get(Node node, K key, int height) {
        if (height == 0) {
            for (int i = 0; i < node.n; i++) {
                K k = node.children[i].key;
                if (key.compareTo(k) == 0) {
                    return node.children[i].value;
                }
            }

            return null;
        }

        for (int i = 0; i < node.n; i++) {
            K k = node.children[i].key;
            if (key.compareTo(k) == 0) {
                return node.children[i].value;
            } else if (key.compareTo(k) < 0) {
                return get(node.children[i].next, key, height - 1);
            }
        }

        return get(node.children[node.n].next, key, height - 1);
    }

    private Node getNode(Node node, K key, int height) {
        if (height == 0) {
            for (int i = 0; i < node.n; i++) {
                K k = node.children[i].key;
                if (key.compareTo(k) == 0) {
                    return node;
                }
            }

            return null;
        }

        for (int i = 0; i < node.n; i++) {
            K k = node.children[i].key;
            if (key.compareTo(k) == 0) {
                return node;
            } else if (key.compareTo(k) < 0) {
                return getNode(node.children[i].next, key, height - 1);
            }
        }

        return getNode(node.children[node.n].next, key, height - 1);
    }


    /**
     * 删除key
     * 1 如果当前节点删除后，如果元素个数>=(M-1)/2，直接返回
     * 2 元素个数<(M-1)/2
     *        如果左节点元素个数>(M-1)/2, 左节点末尾元素移动到父节点，父节点元素移动到当前节点首个元素
     *        左节点元素个数<=(M-1)/2，父节点元素与当前节点和左节点合并
     *
     * 循环操作
     * @param key
     */
    @Override
    public void delete(K key) {
        Node node = getNode(root, key, height);
        if (null == node) {
            return;
        }

        //叶节点直接删除
        if (node.isLeaf() || height == 0) {
            delete(node, key);
        } else {
            //非叶节点先寻找后继，然后转移到后继节点处理
            node = getNext(node, key);
        }

        while (node != root) {
            if (node.n >= (M - 1) / 2) {
                return;
            } else {
                Node parent = node.parent;
                K k = node.children[0].key;

                int i;
                for (i = parent.n - 1; i >= 0; i--) {
                    if (k.compareTo(parent.children[i].key) > 0) {
                        break;
                    }
                }
                int pos = i;
                Node left = parent.children[pos].next;

                //如果左节点元素个数>(M-1)/2, 左节点末尾元素移动到父节点，父节点元素移动到当前节点首个元素
                if (left.n > (M - 1) / 2) {
                    for (i = node.n; i >= 0; i--) {
                        node.children[i + 1] = node.children[i];
                    }
                    node.children[0].key = parent.children[pos].key;
                    node.children[0].value = parent.children[pos].value;
                    node.children[0].next = left.children[left.n].next;
                    node.n++;

                    parent.children[pos].key = left.children[left.n - 1].key;
                    parent.children[pos].value = left.children[left.n - 1].value;

                    left.children[left.n - 1].key = null;
                    left.children[left.n - 1].value = null;
                    left.children[left.n].next = null;
                    left.n--;
                    return;
                } else {
                    //父节点元素与当前节点和左节点合并
                    K k1 = parent.children[pos].key;
                    V v1 = parent.children[pos].value;

                    merge(left, node, k1, v1);
                    delete(parent, k1);

                    node = parent;
                }
            }
        }
    }

    private void delete(Node node, K key) {
        int pos = -1;
        for (int i = 0; i < node.n; i++) {
            K k = node.children[i].key;
            if (key.compareTo(k) == 0) {
                pos = i;
                break;
            }
        }

        if (pos != -1) {
            for (int i = pos; i + 1 < node.n; i++) {
                node.children[i].key = node.children[i+1].key;
                node.children[i].value = node.children[i+1].value;
            }
            for (int i = pos + 1; i + 1 <= node.n; i++) {
                node.children[i].next = node.children[i+1].next;
            }

            node.n--;
            node.children[node.n].key = null;
            node.children[node.n].value = null;
            node.children[node.n + 1].next = null;
        }
    }

    private void merge(Node node, Node right, K key, V value) {
        node.children[node.n].key = key;
        node.children[node.n].value = value;
        node.n++;

        for (int i = 0; i <= right.n; i++) {
            node.children[node.n + i] = right.children[i];
            right.children[i] = null;
        }
        node.n += right.n;
    }

    private Node getNext(Node node, K key) {
        int pos = -1;
        for (int i = 0; i < node.n; i++) {
            K k = node.children[i].key;
            if (key.compareTo(k) == 0) {
                pos = i;
                break;
            }
        }

        Node right = node.children[pos + 1].next;
        while (!right.isLeaf()) {
            right = right.children[0].next;
        }

        node.children[pos].key = right.children[0].key;
        node.children[pos].value = right.children[0].value;

        for (int i = 1; i <= node.n; i++) {
            node.children[i - 1] = node.children[i];
        }
        node.n--;
        node.children[node.n].key = null;
        node.children[node.n].value = null;

        return right;
    }

    @Override
    public List<K> keys() {
        List<K> list = new ArrayList<>(size);
        fillKeys(root, list, height);
        return list;
    }

    private void fillKeys(Node node, List<K> list, int height) {
        if (height == 0) {
            for (int i = 0; i < node.n; i++) {
                list.add(node.children[i].key);
            }
            return;
        }

        for (int i = 0; i < node.n; i++) {
            fillKeys(node.children[i].next, list, height - 1);
            list.add(node.children[i].key);
        }
        fillKeys(node.children[node.n].next, list, height - 1);
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean empty() {
        return size == 0;
    }
}
